// tools/LRParserGenerator.java
package tools;

import java.util.*;

public class LRParserGenerator {
    private final Grammar grammar;

    //first缓存
    private  Map<String, Set<String>> followSets = new HashMap<>();
    //规范族
    private List<Set<LR1Item>> canonicalCollection= new ArrayList<>();
    //用来记录转移关系
    Map<Integer, Map<String, Integer>> transitions= new HashMap<>();

    //action表
    private final Map<Integer, Map<String, String>> actionTable = new HashMap<>();
    //goto表
    private final Map<Integer, Map<String, Integer>> gotoTable = new HashMap<>();
    //状态数
    private int stateCount = 0;

    //构造函数，输入对应的文法，然后构造文法action表和goto表
    public LRParserGenerator(Grammar grammar) {
        this.grammar = grammar;
        GrammarUtils grammarUtils = new GrammarUtils(grammar);
        followSets = grammarUtils.getFollowSets();
        // Step 1: 初始化核心项目集（规范族）
       canonicalCollection = buildCanonicalCollection();
        // Step 3: 生成ACTION/GOTO表
       buildActionAndGotoTables(canonicalCollection);
    }


    //参数初始化

    // 构建规范族（核心项目集）
    private List<Set<LR1Item>> buildCanonicalCollection() {
        Map<Set<LR1Item>, Integer> stateMap = new HashMap<>();
        Queue<Set<LR1Item>> queue = new LinkedList<>();
        List<Set<LR1Item>> canonicalCollection = new ArrayList<>();

        // 1. 初始项目集 S' -> .S, $
        Grammar.Production startRule = grammar.productions.get(0);
        Set<LR1Item> startItems = new HashSet<>();
        startItems.add(new LR1Item(startRule, 0, "$"));
        Set<LR1Item> startClosure = computeClosure(startItems);

        canonicalCollection.add(startClosure);
        stateMap.put(startClosure, 0);
        queue.offer(startClosure);

        while (!queue.isEmpty()) {
            Set<LR1Item> currentState = queue.poll();
            int currentStateId = stateMap.get(currentState);

            // 收集点后符号（项目中dot后面那个符号）
            Set<String> symbols = new HashSet<>();
            for (LR1Item item : currentState) {
                int pos = item.dotPosition;
                if (pos < item.production.rhs.size()) {
                    String nextSymbol = item.production.rhs.get(pos);
                    symbols.add(nextSymbol);
                }
            }

            // 对每个点后符号做goto操作
            for (String symbol : symbols) {
                Set<LR1Item> gotoSet = gotoSet(currentState, symbol);
                if (gotoSet.isEmpty()) continue;

                if (!stateMap.containsKey(gotoSet)) {
                    canonicalCollection.add(gotoSet);
                    int newStateId = canonicalCollection.size() - 1;
                    stateMap.put(gotoSet, newStateId);
                    queue.offer(gotoSet);
                }

                int nextStateId = stateMap.get(gotoSet);
                // 记录状态转移
                transitions.computeIfAbsent(currentStateId, k -> new HashMap<>())
                        .put(symbol, nextStateId);
            }
        }

        return canonicalCollection;
    }


    // 计算项目集闭包（LR(1)核心算法）
    private Set<LR1Item> computeClosure(Set<LR1Item> items) {
        Set<LR1Item> closure = new HashSet<>(items);
        boolean changed;

        do {
            changed = false;
            Set<LR1Item> newItems = new HashSet<>();

            for (LR1Item item : closure) {
                // 如果点没到最右边
                if (item.dotPosition < item.production.rhs.size()) {
                    String symbol = item.production.rhs.get(item.dotPosition);
                    // 如果是非终结符
                    if (grammar.nonTerminals.contains(symbol)) {
                        // 简化：直接用当前项目的nextSymbol作为新项目的lookahead
                        String lookahead = item.nextSymbol;

                        // 对symbol的所有产生式添加新项目
                        for (Grammar.Production prod : grammar.productions) {
                            if (prod.lhs.equals(symbol)) {
                                LR1Item newItem = new LR1Item(prod, 0, lookahead);
                                if (!closure.contains(newItem)) {
                                    newItems.add(newItem);
                                }
                            }
                        }
                    }
                }
            }

            if (!newItems.isEmpty()) {
                closure.addAll(newItems);
                changed = true;
            }
        } while (changed);

        return closure;
    }




    private Set<LR1Item> gotoSet(Set<LR1Item> items, String symbol) {
        Set<LR1Item> movedItems = new HashSet<>();

        for (LR1Item item : items) {
            // 点后符号是目标符号，点右移一位
            if (item.dotPosition < item.production.rhs.size() &&
                    symbol.equals(item.production.rhs.get(item.dotPosition))) {

                LR1Item movedItem = new LR1Item(
                        item.production,
                        item.dotPosition + 1,
                        item.nextSymbol  // 保持使用 nextSymbol 字段
                );
                movedItems.add(movedItem);
            }
        }

        // 计算闭包
        return computeClosure(movedItems);
    }



    // 生成ACTION/GOTO表
    private void buildActionAndGotoTables(List<Set<LR1Item>> collection) {
        for (int state = 0; state < collection.size(); state++) {
            Set<LR1Item> items = collection.get(state);
            Map<String, String> actions = new HashMap<>();
            Map<String, Integer> goTos = new HashMap<>();

            for (LR1Item item : items) {
                if (item.dotPosition < item.production.rhs.size()) {
                    // 点后符号
                    String symbol = item.production.rhs.get(item.dotPosition);

                    // 移进或GOTO：通过转移表找下个状态
                    Integer nextState = null;
                    Map<String, Integer> trans = transitions.get(state);
                    if (trans != null) {
                        nextState = trans.get(symbol);
                    }
                    if (nextState == null) continue; // 没转移不处理

                    if (grammar.terminals.contains(symbol)) {
                        // 终结符 => 移进
                        actions.put(symbol, "s" + nextState);
                    } else if (grammar.nonTerminals.contains(symbol)) {
                        // 非终结符 => GOTO
                        goTos.put(symbol, nextState);
                    }
                } else {
                    // 点已到右边，归约动作
                    // 如果是增强文法的开始产生式，接受动作
                    if (item.production.lhs.equals(grammar.startSymbol)) {
                        actions.put("$", "acc");
                    } else {
                        // 用该产生式左部的 FOLLOW 集合作为归约符号集
                        Set<String> follows = followSets.get(item.production.lhs);
                        if (follows == null) continue; // 无follow则跳过

                        int ruleIndex = grammar.productions.indexOf(item.production);
                        for (String lookahead : follows) {
                            // 避免冲突可以检查是否已有动作
                            if (actions.containsKey(lookahead)) {
                                // 这里可加冲突处理逻辑
                            }
                            actions.put(lookahead, "r" + ruleIndex);
                        }
                    }
                }
            }

            actionTable.put(state, actions);
            gotoTable.put(state, goTos);
        }
    }




    public List<Set<LR1Item>> getCanonicalCollection(){
        return canonicalCollection;
    }


    // 获取ACTION表
    public Map<Integer, Map<String, String>> getActionTable() {
        return actionTable;
    }

    // 获取GOTO表
    public Map<Integer, Map<String, Integer>> getGotoTable() {
        return gotoTable;
    }






    //LR(1)项目类
    private static class LR1Item {
        final Grammar.Production production;
        final int dotPosition;

        //下一个字符
        final String nextSymbol;

        LR1Item(Grammar.Production production, int dotPosition, String nextSymbol) {
            this.production = production;
            this.dotPosition = dotPosition;
            this.nextSymbol = nextSymbol;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            LR1Item item = (LR1Item) o;
            return dotPosition == item.dotPosition &&
                    production.equals(item.production) &&
                    nextSymbol.equals(item.nextSymbol);
        }

        @Override
        public int hashCode() {
            return Objects.hash(production, dotPosition, nextSymbol);
        }
    }
}
